/**
 * 版权所有 2009-2012山东新北洋信息技术股份有限公司
 * 保留所有权利。
 */
package com.linyaonan.leetcode.medium._13;

import java.util.LinkedList;

/**
 * 地上有一个m行n列的方格，从坐标 [0,0] 到坐标 [m-1,n-1] 。
 * 一个机器人从坐标 [0, 0] 的格子开始移动，它每次可以向左、右、上、下移动一格（不能移动到方格外），
 * 也不能进入行坐标和列坐标的数位之和大于k的格子。例如，当k为18时，机器人能够进入方格 [35, 37] ，
 * 因为3+5+3+7=18。但它不能进入方格 [35, 38]，因为3+5+3+8=19。请问该机器人能够到达多少个格子？
 * <p>
 * <p>
 * 示例 1：
 * <p>
 * 输入：m = 2, n = 3, k = 1
 * 输出：3
 * 示例 1：
 * <p>
 * 输入：m = 3, n = 1, k = 0
 * 输出：1
 * 提示：
 * <p>
 * 1 <= n,m <= 100
 * 0 <= k <= 20
 *
 * @ProjectName: leetcode
 * @Package: com.linyaonan.leetcode.medium._13
 * @ClassName: MovingCount
 * @Author: linyaonan
 * @Date: 2020/4/8 11:45
 */
public class MovingCount {

    public int movingCount(int m, int n, int k) {
        // 当k==0时，只能走一个
        if (k == 0) {
            return 1;
        }
        int count = 1;
        // 可以移动4个方向
        int[] x = new int[]{0, 0, 1, -1};
        int[] y = new int[]{1, -1, 0, 0};
        // 原始棋盘
        int[][] org = new int[m][n];
        org[0][0] = 1;
        LinkedList<int[]> stack = new LinkedList<>();
        stack.add(new int[]{0, 0});
        while (!stack.isEmpty()) {
            int[] point = stack.poll();
            if (point != null) {
                for (int i = 0; i < 4; i++) {
                    int xPonint = point[0] + x[i];
                    int yPonint = point[1] + y[i];
                    // 边界与相加数值满足条件
                    if (checkIsVailde(xPonint, yPonint, m - 1, n - 1, k, org)) {
                        org[xPonint][yPonint] = 1;
                        stack.add(new int[]{xPonint, yPonint});
                        count++;
                    }
                }
            }
        }
        return count;
    }

    private static boolean checkIsVailde(int x, int y, int xMax, int yMax, int k, int[][] org) {
        // 坐标满足
        if (x >= 0 && x <= xMax && y >= 0 && y <= yMax) {
            // 位数相加满足
            if (org[x][y] == 0) {
                return getAddNum(x) + getAddNum(y) <= k;
            }
        }
        return false;
    }

    /**
     * 获取每一位相加得到的数值
     *
     * @param num
     * @return
     */
    private static int getAddNum(int num) {
        int add = 0;
        while (num >= 10) {
            add += num % 10;
            num = num / 10;
        }
        add += num;
        return add;
    }
}
